<?php
/*
 * 龙与地下城游戏问题
 * 【题目】
 * 给定一个二维数组 map，含义是一张地图，例如，如下矩阵:
 * -2 -3 3
 * -5 -10 1
 * 0 30 -5
 * 游戏的规则如下:
 * 骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
 * 地图中每个位置的值代表骑士要遭遇的事情。
 * 如果是负数，说明此处有怪兽，要让骑士损失血量。
 * 如果是非负数，代表此处有血瓶，能让骑士回血。
 * 骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。
 * 为了保证骑士能见到公主，初始血量至少是多少?
 * 根据 map，返回初始血量。
 */

$matrix =  [
    [-2, -3, 3,],
    [-5, -10, 1,],
    [0, 30, -5,],
];
$obj = new Middle_Day08_Code_02();
$res = $obj->main($matrix);
echo $res;


class Middle_Day08_Code_02
{
    /*
        如果m[i][j]是正数，那么能走上这一单元格的条件就是血量 > 0
        如果m[i][j]是负数，那么能走上这一单元格的条件就是血量 = abs(m[i][j]) + 1，保证能往下一格走
    */
    public function main($m)
    {
        if ($m == null || $m.length == 0 || $m[0] == null || $m[0].length == 0) {
            return 1;
        }
        $row = count($m);
		$col = count($m[0]);
		$dp = array_fill(0, $row--, array_fill(0, $col--, 0));
		// 最右下角终点需要的最少血量
		$dp[$row][$col] = $m[$row][$col] > 0 ? 1 : -$m[$row][$col] + 1;
		// 最下边一行的最少血量，只需要看右侧格子即可
		for ($j = $col - 1; $j >= 0; $j--) {
            $dp[$row][$j] = max($dp[$row][$j + 1] - $m[$row][$j], 1);
        }
		for ($i = $row - 1; $i >= 0; $i--) {
            // 最右边一列的最少血量，只需要看下方格子即可
            $dp[$i][$col] = max($dp[$i + 1][$col] - $m[$i][$col], 1);

            // 常规格子
            for ($j = $col - 1; $j >= 0; $j--) {
                /*
                 * 往右走，如果右边格子的要求血量是7
                 * 如果m[i][j]是血瓶4，那么这一格的最低血量就是3
                 * 如果m[i][j]是血瓶10，那么这一格的最低血量就是1
                 * 如果m[i][j]是怪兽-3，那么这一格的最低血量就是10
                 * 如果m[i][j]是怪兽-10，那么这一格的最低血量就是17
                 */
                $right = max($dp[$i][$j + 1] - $m[$i][$j], 1);
                // 往下走和往右走的条件一样
                $down = max($dp[$i + 1][$j] - $m[$i][$j], 1);
                $dp[$i][$j] = min($right, $down);
            }
		}
		return $dp[0][0];
    }


}